//
// Created by zzx on 2022/10/6.
//

#ifndef QTCREATERHELLO_SOLVE24GAME_H
#define QTCREATERHELLO_SOLVE24GAME_H

#include <iostream>
#include <vector>
#include <cmath>


namespace std {
class Solve24Game {
    public:
        static constexpr int TARGET = 24;
        static constexpr double EPSILON = 1e-6;
        static constexpr int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
        vector<string>ans;

        vector<string> getAns(vector<int> &nums) {
            ans.clear();
            vector<double> l;
            for (const int &num : nums) {
                l.emplace_back(static_cast<double>(num));
            }
            if (solve(l)) {
                return ans;
            }
            return {};
        }

        bool solve(vector<double> &nums) {
            if (nums.size() == 0) {
                return false;
            }
            if (nums.size() == 1) {
                return abs(nums[0] - TARGET) < EPSILON;
            }
            int size = nums.size();
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (i != j) {
                        vector<double> nextNums = vector<double>();
                        for (int k = 0; k < size; k++) {
                            if (k != i && k != j) {
                                nextNums.emplace_back(nums[k]);
                            }
                        }
                        for (int k = 0; k < 4; k++) {
                            if (k < 2 && i > j) {
                                continue;
                            }
                            double a = nums[i], b = nums[j];
                            char arr[100];
                            if (k == ADD) {
                                sprintf(arr, "%.02f + %.02f = %.02f", a, b, a + b);
                                ans.push_back(string(arr));
                                nextNums.emplace_back(a + b);
                            } else if (k == MULTIPLY) {
                                sprintf(arr, "%.02f * %.02f = %.02f", a, b, a * b);
                                ans.push_back(string(arr));
                                nextNums.emplace_back(a * b);
                            } else if (k == SUBTRACT) {
                                sprintf(arr, "%.02f - %.02f = %.02f", a, b, a - b);
                                ans.push_back(string(arr));
                                nextNums.emplace_back(a - b);
                            } else if (k == DIVIDE) {
                                if (fabs(nums[j]) < EPSILON) {
                                    continue;
                                }
                                sprintf(arr, "%.02f / %.02f = %.02f", a, b, a / b);
                                ans.push_back(string(arr));
                                nextNums.emplace_back(a / b);
                            }
                            if (solve(nextNums)) {
                                return true;
                            }
                            nextNums.pop_back();
                            ans.pop_back();
                        }
                    }
                }
            }
            return false;
        }
};

};


#endif //QTCREATERHELLO_SOLVE24GAME_H
